# LeetCode 150、逆波兰表达式求值
# 一、题目描述
根据 逆波兰表示法 (opens new window)，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
提示：
1 <= tokens.length <= 10^4tokens[i]是一个算符（"+"、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 逆波兰表达式求值（LeetCode 150）：https://leetcode.cn/problems/evaluate-reverse-polish-notation/
class Solution {
public int evalRPN(String[] tokens) {
// 使用一个栈存储操作数，从左到右遍历逆波兰表达式
Stack<Integer> result = new Stack<>();
// 对于一个表达式来说，由两个操作数和一个运算符构成
// 比如加法：① ＋ ②
// 比如减法：① - ②
// 比如乘法：① * ②
// 比如除法：① / ②
// 先出栈的是右操作数，后出栈的是左操作数
// 先出栈的是右操作数
int rightNum;
// 后出栈的是左操作数
int leftNum;
// 一个表达式的计算结果
int ans;
// 遍历字符串数组
for(String token : tokens){
// 如果是 +
if("+".equals(token)){
// 先出栈的是右操作数
rightNum = result.pop();
// 后出栈的是左操作数
leftNum = result.pop();
// 计算结果
ans = leftNum + rightNum;
// 如果是 -
}else if("-".equals(token)){
// 先出栈的是右操作数
rightNum = result.pop();
// 后出栈的是左操作数
leftNum = result.pop();
// 计算结果
ans = leftNum - rightNum;
// 如果是 *
}else if("*".equals(token)){
// 先出栈的是右操作数
rightNum = result.pop();
// 后出栈的是左操作数
leftNum = result.pop();
// 计算结果
ans = leftNum * rightNum;
// 如果是 /
}else if("/".equals(token)){
// 先出栈的是右操作数
rightNum = result.pop();
// 后出栈的是左操作数
leftNum = result.pop();
// 计算结果
ans = leftNum / rightNum;
// 如果是非运算符
}else{
// 转换为数字
ans = Integer.valueOf(token);
}
// 存储结果
result.push(ans);
}
// 返回栈顶元素
return result.pop();
}
}
# 2、C++ 代码
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 使用一个栈存储操作数，从左到右遍历逆波兰表达式
stack<int> result;
// 对于一个表达式来说，由两个操作数和一个运算符构成
// 比如加法：① ＋ ②
// 比如减法：① - ②
// 比如乘法：① * ②
// 比如除法：① / ②
// 先出栈的是右操作数，后出栈的是左操作数
// 先出栈的是右操作数
long int rightNum;
// 后出栈的是左操作数
long int leftNum;
// 一个表达式的计算结果
long int ans;
// 遍历字符串数组
for (int i = 0; i < tokens.size(); i++) {
// 如果是 +
if(tokens[i] == "+"){
// 先出栈的是右操作数
rightNum = result.top();
result.pop();
// 后出栈的是左操作数
leftNum = result.top();
result.pop();
// 计算结果
ans = leftNum + rightNum;
// 如果是 -
}else if(tokens[i] == "-"){
// 先出栈的是右操作数
rightNum = result.top();
result.pop();
// 后出栈的是左操作数
leftNum = result.top();
result.pop();
// 计算结果
ans = leftNum - rightNum;
// 如果是 *
}else if(tokens[i] == "*"){
// 先出栈的是右操作数
rightNum = result.top();
result.pop();
// 后出栈的是左操作数
leftNum = result.top();
result.pop();
// 计算结果
ans = leftNum * rightNum;
// 如果是 /
}else if(tokens[i] == "/"){
// 先出栈的是右操作数
rightNum = result.top();
result.pop();
// 后出栈的是左操作数
leftNum = result.top();
result.pop();
// 计算结果
ans = leftNum / rightNum;
// 如果是非运算符
}else{
// 转换为数字
ans = stoi(tokens[i]);
}
// 存储结果
result.push(ans);
}
// 返回栈顶元素
return result.top();
}
};
# 3、Python 代码
class Solution(object):
def evalRPN(self, tokens):
stack = []
for token in tokens:
try:
stack.append(int(token))
except:
num2 = stack.pop()
num1 = stack.pop()
stack.append(self.evaluate(num1, num2, token))
return stack[0]
def evaluate(self, num1, num2, op):
if op == "+":
return num1 + num2
elif op == "-":
return num1 - num2
elif op == "*":
return num1 * num2
elif op == "/":
return int(num1 / float(num2))